import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Stack;
// 最小的K个数
public class Solution {
    /**
     * @param input int整型一维数组
     * @param k int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        ArrayList<Integer> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        if(k == 0){
            return list;
        }
        //先找k次，将前k个数据放入堆中
        for(int i = 0; i < k; i++){
            queue.add(input[i]);
        }
        //接着将从k到数组末尾的数据一次与堆顶元素比较
        for(int i = k; i < input.length;i++){
            if(input[i] < queue.peek()){
                queue.poll();
                queue.add(input[i]);
            }
        }
        while(!queue.isEmpty()){
            stack.push(queue.poll());
        }
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }
}